package doublelinkedlist;

/**
 * @author tongchen
 * @create 2022-10-15 14:13
 */
public class DoubleLInkedList {
    public static void main(String[] args) {
        DoubleLInkedList doubleLInkedList = new DoubleLInkedList();
        doubleLInkedList.addLast(1);
        doubleLInkedList.addFirst(1);
        doubleLInkedList.addFirst(2);
        doubleLInkedList.addLast(1);
        doubleLInkedList.addLast(20);
        doubleLInkedList.addLast(56);
        doubleLInkedList.addLast(34);
        doubleLInkedList.addLast(1);
        doubleLInkedList.addFirst(1);
        doubleLInkedList.display();
        System.out.println(doubleLInkedList.size());
        doubleLInkedList.addIndex(5,32);
        doubleLInkedList.display();
        System.out.println(doubleLInkedList.size());
        doubleLInkedList.remove(1);
        doubleLInkedList.display();
        System.out.println("***********************************");
        doubleLInkedList.removeAllKey(1);
        doubleLInkedList.display();
        System.out.println(doubleLInkedList.size());
        System.out.println(doubleLInkedList.contains(2));


    }
    ListNode head;
    ListNode tail;

    //头插法
    public void addFirst(int data) {
        //创建结点
        ListNode node = new ListNode(data);
        //处理链表为空的情况
        if (head == null) {
            head = node;
            tail = node;
        } else {
            head.pre = node;
            head.pre.next = head;
            head = head.pre;
        }

    }

    //尾插法
    public void addLast(int data) {
//处理链表为空的情况
        ListNode listNode = new ListNode(data);
        if(head==null){
            head=listNode;
            tail=listNode;
        }
        else{
            tail.next=listNode;
            tail.next.pre=tail;
            tail=tail.next;
        }
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        //对链表和index进行合法性的校验
        if(head==null){
            throw new RuntimeException("链表为空");
        }
        if(index<0||index>size()){
            throw new RuntimeException("输入的下标不合法");
        }
//如果是第一个和最后一个位置，直接使用头插法和尾插法即可
        if(index==0){
            addFirst(data);
        } else if (index==size()) {
            addLast(data);
        }
        else {
            ListNode listNode = new ListNode(data);
            int count=0;//进行记录
            ListNode cur=head;
            while(count++!=index){
                cur=cur.next;
            }
            cur.pre.next=listNode;
            listNode.pre=cur.pre;
            cur.pre=listNode;
            listNode.next=cur;
        }
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        if(head==null){
            return  false;
        }
        ListNode cur=head;
        while(cur!=null){
            if (cur.val!=key){
                cur=cur.next;
            }
            else {
                return true;
            }
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if(head==null){
            throw new RuntimeException("链表为空");
        }
        //处理头结点情况
        if (head.val==key){
            if(head.next==null){
                head= null;
            } else {
                head=head.next;
                head.pre=null;
            }
            return;

        }
        //处理中间结点
        ListNode cur=head;

            while (cur!=null&&cur.next!=null){
                if(cur.val==key){
                    cur.pre.next=cur.next;
                    cur.next.pre=cur.pre;
                    return;
                }
            }
            //处理尾结点
        if(cur.next==null&&cur.val==key){
            cur.pre.next=null;
            cur.pre=null;
            return;
        }
            cur=cur.next;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if(head==null){
            throw new RuntimeException("链表为空");
        }
        //处理头结点情况
        while (head.val==key){
            if(head.next==null){
                head= null;
                if(head==null){
                    throw new RuntimeException("链表为空");
                }
            } else {
                head=head.next;
                head.pre=null;
            }


        }
        //处理中间结点
        ListNode cur=head;

        while (cur!=null&&cur.next!=null){
            if(cur.val==key){
                cur.pre.next=cur.next;
                cur.next.pre=cur.pre;

            }
            cur=cur.next;
        }
        //处理尾结点
        if(cur.next==null&&cur.val==key){
            cur.pre.next=null;
            cur.pre=null;

        }


    }

    //得到单链表的长度
    public int size() {
        int count=0;
        if(head==null){
            return 0;
        }
        ListNode cur=head;
        while(cur!=null){
            cur=cur.next;
            count++;
        }
        return count;
    }

    public void clear() {
        head=null;
    }

    //对链表进行展览
    public void display() {
//判断链表是否为空
        if (head==null) {
            System.out.println(
                    "链表为空，无法进行打印"
            );
        }
            ListNode cur=head;
            while(cur!=null){
                System.out.println(cur);
                cur=cur.next;
            }

    }
}

class ListNode {
    int val;
    ListNode pre;
    ListNode next;

    //默认其前一个跟后一个节点为null
    public ListNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val  +
                '}';
    }
}
